package leetCode.solution;

import java.util.Arrays;
import java.util.Random;

import com.alibaba.fastjson.JSON;

public class Solution881 {
	
	 public int numRescueBoats1(int[] people, int limit) {
	        Arrays.sort(people);
	        int n = people.length;
	        int i = 0, j = n - 1;
	        while (i < j) {
	            if (people[j] + people[i] <= limit) {
	                i++;
	            }
	            j--;
	        }
	        return n - i;
	    }
	 
	public int numRescueBoats(int[] people, int limit) {
		int count = 0;
//		Arrays.sort(people);
		mySort(people);
		int n = people.length;
		if(people[n-1]>limit) return Integer.MAX_VALUE;
		int i=0;
		while(i<n) {
			if(people[i]+people[n-1]>limit) {
				count++;
				n--;
			}else {
				count++;
				n--;
				i++;
			}
		}
		return count;
	}
	
	public int[] mySort(int[] people){
		if(people==null || people.length<=1) return people;
		quickSort(people, 0, people.length-1);
		return people;
	}
	
	private static void quickSort(int[] nums, int l, int r) {
		if(l<r) {
			int range[] = partition(nums, l, r);
			quickSort(nums, l, range[0]-1);
			quickSort(nums, range[1]+1, r);
		}
	}
	
	private static int[] partition(int[] nums, int l, int r) {
		int mid = nums[l + new Random().nextInt(r - l + 1)];
		int i = l;
		while(i<=r) {
			if(nums[i]>mid) {
				swap(nums, i, r--);
			}else if(nums[i]<mid) {
				swap(nums, l++, i++);
			}else {
				i++;
			}
		}
		return new int[]{l,i-1};
	}
	
	private static void swap(int[] nums, int m, int n) {
		int temp = nums[m];
		nums[m]=nums[n];
		nums[n]= temp;
	}
}
